In object oriented programming languages, such as Java, a subclass inherits the methods of its parent class. Thus, if class B is a subclass of class A, and class A has a method “foo”, then class B also has a method foo. In most object oriented languages, it is also possible for a subclass to override the method implementation provided by its parent class. Thus, class B can provide a different implementation for method foo than that provided by class A. Because methods can be overridden, it is not possible at compile time to determine which implementation to invoke when method foo is called. If foo is called on an object that is an instance of class A, then the implementation provided by class A should be invoked, but if foo is called on an object that is an instance of class B, then the implementation provided by class B should be invoked. Because of this uncertainty, the implementation of foo to invoke needs to be determined at runtime. Methods, such as foo, that can be implemented by multiple classes, and the implementations for which need to be determined at runtime, are referred to as virtual methods.
The process of determining which implementation of a virtual method to invoke at runtime is known as virtual method dispatch. This process is typically carried out using virtual method dispatch tables (vtables). Usually, a vtable is created for each class. In the above example, class A has its own vtable and class B has its own vtable. Class A's vtable has an entry that points to the implementation for method foo provided by class A. Class B's vtable has an entry that points to the implementation for method foo provided by class B. At runtime, when method foo is called on an object, a determination is made as to the class of that object. If the object is of class A, then class A's vtable is used to perform the method dispatch, which results in class A's implementation for foo being invoked. On the other hand, if the object is of class B, then class B's vtable is used to perform the method dispatch, which results in class B's implementation for foo being invoked. In this manner, the proper implementation for foo is determined and invoked at runtime.
Typically, a vtable is created for a class at the time that the class is loaded. In some implementations, all classes within an application are loaded at the time the application is loaded. In other implementations, classes are loaded as they are referenced by the application. In either case, creating a vtable for a class at the time that the class is loaded can lead to the creation of many vtables (some applications can have hundreds or even thousands of classes loaded at a time). Because vtables often need to be updatable, vtables are often stored in RAM, a very expensive type of storage. The more vtables that need to be created, the more RAM that is required, and the higher the cost of a device or system.
Another problem associated with having a large number of vtables is that of performance degradation. In many implementations (e.g. Java implementations), the information in vtables is updated fairly regularly. For example, in a system that implements garbage collection, a set of code may be moved from one location of the memory heap to another as part of the garbage collection operation. When this happens, all of the vtables that contain a pointer to that set of code need to be updated to point to the new location. If there is a large number vtables, and if the movement of the set of code affects a large number of these vtables, then the updating of the vtables could take a very long time. This in turn could have a significant adverse impact on the overall performance of the system.